package org.kfive.nova.algorithm;

/**
 * TODO
 *
 * @author zhanwu.lzw
 * @date 2018年06月06日 7:47
 */
public class MaxPQ<Key extends Comparable<Key>> {

    private Key[] keys;

    private Integer size;

    public MaxPQ(Key[] keys) {
        this.keys = (Key[]) new Comparable[keys.length + 1];
        this.size = keys.length + 1;
    }

    void insert(Key key) {
        keys[++size] = key;
        swim(size);
    }

    Key max() {
        return keys[1];
    }

    Key delMax() {
        Key key = keys[1];
        exch(1,size--);
        keys[size+1]=null;
        sink(1);
        return key;
    }

    boolean isEmpty() {
        return size==0;
    }

    int size() {
        return size;
    }

    private boolean less(Key key1, Key key2) {
        return key1.compareTo(key2) < 0;
    }

    private void exch(int i, int j) {
        Key t = keys[i];
        keys[i] = keys[j];
        keys[j] = t;
    }

    private void swim(int i){
        while (i>1 && less(keys[i/2],keys[i])){
            exch(i,i/2);
            i = i/2;
        }
    }

    private void sink(int i){
        while (2*i<=size){
            int j = 2*i;
            if(j<size && less(keys[j],keys[j+1])){
                j++;
            }
            if(!less(keys[i],keys[j])){
                break;
            }
            exch(i,j);
            i = j;
        }
    }
}
